﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//1177. 构建回文串检测❤️
// 这样可以将字符串s看成一个数组，然后统计数组的异或前缀和count,这样就可以统计每一个字母的奇偶性。
// 遍历所有queries, 待检子串都可以表示为[left, right, k]。利用异或前缀和数组,可以得到待检子每一个字母的奇偶性。
//出现偶数次的字母，可以对称放在字符串两侧，构成回文串，剩下的出现奇数次字母配对后，还会剩余，要从中选择最多k项替换成任何小写英文字母。
//替换k次,可以保证使得长度最长为2x k+ 1的字符串变成回文串。所以我们只需要判断，待检子串的为1数位，别于2xk+1即可。

class Solution {
public:
	vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
		int n = s.size();
		vector<int> count(n + 1);
		for (int i = 0; i < n; i++)
		{//异或前缀和
			count[i + 1] = count[i] ^ (1 << (s[i] - 'a'));
		}
		for (int i = 1; i <= n; i++) {
			cout << count[i] << endl;
		}
		vector<bool> res;
		for (auto& query : queries) {
			int l = query[0], r = query[1], k = query[2];
			//bits为多少就代表有多少个奇数次字母
			int bits = 0, x = count[r + 1] ^ count[l];
			// cout<<x<<endl;
			while (x > 0) {
				x &= x - 1;
				bits++;
			}
			//只要bits小于2*k+1那么就可以替换成回文子串
			res.push_back(bits <= k * 2 + 1);
		}
		return res;
	}
};

//剑指 Offer II 051. 节点之和最大的路径❤️
class Solution {
public:
	int maxValue = INT_MIN;
	int GetMax(TreeNode* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		//左右节点的值小于0，就取0，相当于不取分支节点的路径
		int leftvalue = max(GetMax(root->left), 0);
		int rightvalue = max(GetMax(root->right), 0);

		int curValue = root->val + leftvalue + rightvalue;

		maxValue = max(curValue, maxValue);//更新节点最大值

		//返回左右路径最大的那一条
		return root->val + max(leftvalue, rightvalue);

	}
	int maxPathSum(TreeNode* root) {
		maxValue = max(GetMax(root), maxValue);
		return maxValue;
	}
};